#include "Tree.h"
#include "InternalNode.h"
#include "LeafNode.h"
#include <iostream>
#include <map>

using namespace std;

Tree::Tree(void)
{
	//root = new InternalNode(0); //NYT node
	//valuesMap = map<int,LeafNode*>();
	//valuesMap.insert(valuesMap.begin(), pair<int,LeafNode*>(-1,root));	
}

Tree::~Tree(void)
{
	// empty destructor
}

void Tree::add(int elem) {

	if ( false ){		

	} else {
		//Node* nytNode = find(-1); //find NYT
		//LeafNode* leafNode = new LeafNode(0, elem); //leafNode first, get higher order
		//InternalNode* parentNode = new InternalNode(0);		
		//parentNode->setLeft(nytNode);
	 //   parentNode->setRight(leafNode);		


	/*	nytNode->swapData(parentNode); 

		leafsMap.insert(leafsMap.begin(), pair<int,LeafNode*>(elem,leafNode));				
		checkUp(leafNode);*/
	}
	return; 
}

Node* Tree::addNode(int val) {

	// iterate ovar all bits in value
	Node* newNode = 0;
	Node* parentNode = root;
	int counter;

	for(counter = 15; counter >= 0; counter--) {
		if(val && (1 << counter)) {
			parentNode = parentNode -> getRight();
		} else {
			parentNode = parentNode -> getLeft();
		}
	}

	// create new node	

	// if the parent hasn't been found than add node to root
	if(parentNode == 0) {
		root = newNode;
	} else {
		// TODO this is prabobly the place where the tree should be splited
		// TODO depending on the last bit, set the left or right child
		if(val % 2) {
			// parentNode -> setRight(newNode);
		} else {
			// parentNode -> setLeft(newNode);
		}
	}

	return newNode;
}

Node* Tree::getNodeByVal(int val) {

	// TODO this could be optimed by using the map of nodes

	// iterates over all bits in tree starting from the most significant
	// and moves through the tree nodes in other to find the proper symbol	
	int counter;
	Node* node = root;

	for(counter = 15; counter >= 0; counter--) {	
		if(node -> isLeaf()) {
			break;
		}

		if(val && (1 << counter)) {
			// if the bit on specified position is set the move to the right child
			node = node -> getRight();
		} else {
			// otherwise move to the left child
			node = node -> getLeft();
		}
	}

	// check if the symbol has been found and return the coresponding node
	if(counter < 0) {
		return node;
	}

	// otherwise return null to indicate that the symbol hasn't been found
	return 0;
}

//LeafNode* tree::find(int elem){	
//	/* zdejmij wierzcholek z kolejki */
//	Node* node;
//	if ( valuesMap.find(elem) != valuesMap.end() ){
//		node = valuesMap[elem];
//	} else {
//		return NULL;
//	}
//}

//void Tree::checkUp(Node* node){
//	Node* parent = node->getParent();
//	if ( parent == root)
//		return;
//	return;
//}

/*
void huff_increment (HCoder *huff, unsigned node)
{
unsigned next, up = huff->table[node].up;

  //  obviate swapping a parent with its child:
  //    increment the leaf and proceed
  //    directly to its parent.

  if( huff->table[node].next == up )
      huff->table[node].weight += 2;
  else
      up = node;

  //  slide right and go up until reaching the root

  while( node = up, huff->table[node].up ) {
    next = huff->table[node].next;

    //  promote the node to group leader
    //  position by sliding right over
    //  any equal weight nodes

    while( huff->table[node].weight == huff->table[next].weight )
        next = huff_slide (huff, node, next);

    //  increase the weight of the node

    huff->table[node].weight += 2;

    //  internal nodes go up from this
    //  initial group leader position

    if( node > huff->size )
        up = huff->table[node].up;

    //  slide incremented node over smaller weights to its right

    while( huff->table[node].weight > huff->table[next].weight )
        next = huff_slide (huff, node, next);

    //  symbol nodes slide over first,
    //  then go up from their
    //  final positions

    if( node < huff->size )
        up = huff->table[node].up;
  }

  //  increase the root's weight

  huff->table[node].weight += 2;
}
*/

void Tree::incrementNodes(Node* node) {


}